package com.peng.leetcode.list;

/**
 * RreorderList
 * 剑指 Offer II 026. 重排链表
 * https://leetcode.cn/problems/LGjMqU/
 * 重排序链表
 *  L0 → L1 → … → Ln-1 → Ln
 *  L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
 *  寻找中心节点
 *  反转链表的后半部分
 *  合并链表
 *
 * @author: lupeng6
 * @create: 2020/12/31 15:01
 */
public class ReorderList {

    public static void main(String[] args) {
        ListNode listNode = BuildListNode.tailInsert(1, 2, 3, 4, 5);
        new ReorderList().reorderList(listNode);
        PrintListNode.print(listNode);
    }


    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        // 快慢指针找到中间节点
        ListNode low = findMiddle(head);
        ListNode afterSegment = low.next;
        low.next = null;
        ListNode tail = reverse(afterSegment);
        ListNode current = new ListNode(-1);
        while (head != null && tail != null) {
            current.next = head;
            head = head.next;
            current.next.next = tail;
            tail = tail.next;
            current = current.next.next;
        }
        if (head != null) {
            current.next = head;
        }
        if (tail != null) {
            current.next = tail;
        }
    }

    private static ListNode findMiddle(ListNode head) {
        ListNode low = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            low = low.next;
            fast = fast.next.next;
        }
        return low;
    }

    public static ListNode reverse(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode newHead = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        return newHead;
    }
}
